DEFINITION MODULE  Stacks;

(*****************************************************************************)
(* Dieses Modul enthaelt Prozeduren zur Erzeugung und Verwaltung eines       *)
(* Stacks (LIFO - List ). Die Stackoperationen sind nicht an einen bestimm-  *)
(* ten Datentyp gebunden, d.h. aber auch, dass keine Typueberpruefung - we-  *)
(* der zur Uebersetzungszeit noch zur Laufzeit - vorgenommen wird.           *)
(*                                                                           *)
(* Um jedoch eine kleine Ueberpruefung zu ermoeglichen, muss bei Einrichtung *)
(* eines Stacks der Speicherplatz der Elemente angegeben werden, fuer die der*)
(* Stack genutzt werden soll; Wird zur Laufzeit beim Hinzufuegen oder Ent-   *)
(* fernen ein Element mit einer anderen Speicherplatzgroesse benutzt, wird   *)
(* dies als Fehler erkannt ( --> sizeErr ).                                  *)
(*                                                                           *)
(* Als weitere Notbremse pruefen alle Prozeduren, ob der Stack, der ihnen    *)
(* uebergeben wird, einen undefinierten Wert hat. Auch hier wird ein Fehler  *)
(* erkannt ( --> defErr ).                                                   *)
(*                                                                           *)
(* Wird ein beliebiger Fehler erkannt, wird dies ueber den Parameter <done>  *)
(* mitgeteilt; eine detailliertere Fehlermeldung erhaelt man ueber die Proze-*)
(* dur "LastStackResult". Auf Wunsch kann auch mit "AssignStackHandler" eine *)
(* automatische Fehlerbehandlung durch das Modul erfolgen.                   *)
(*                                                                           *)
(* Wegen der Pruefung auf undefinierten Stack muessen saemtliche Parameter   *)
(* vom Typ Stack als VAR-Parameter uebergeben werden, obwohl sie manchmal    *)
(* nur Eingangsparameter sind ( siehe Kommentar ).                           *)
(*                                                                           *)
(* Die vorliegende MODULA-2 - Implementation erlaubt nur das Ablegen von     *)
(* einzelnen Variablen auf dem Stack; nicht erlaubt sind Ausdruecke - auch   *)
(* keine Konstanten. Ausdruecke muessen also erst berechnet und einer Varia- *)
(* blen zugewiesen werden, bevor ihr Wert auf dem Stack gespeichert werden   *)
(* kann.                                                                     *)
(*___________________________________________________________________________*)
(*   23-Feb-90 , Holger Kleinschmidt                                         *)
(*****************************************************************************)

FROM  SYSTEM  IMPORT  BYTE;

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)

   TYPE
         Stack;     (* mehr braucht man nicht zu wissen -> OPAK (ADT)  *)

         StackResult  = ( stackOk, defErr, sizeErr, noMem, stackEmpty );

         StackHandler = PROCEDURE ((* EIN  proc  *) ARRAY OF CHAR,
                                   (* EIN  stErr *) StackResult   );

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)

  PROCEDURE  AssignStackHandler ((* EIN/  -- *) handler : StackHandler );

  PROCEDURE  UnAssignStackHandler;

 (*-------------------------------------------------------------------------
  | Ist mit "AssignStackHandler" eine Fehlerbehandlungsroutine definiert    |
  | worden, so wird diese jedesmal automatisch aufgerufen, wenn bei einer   |
  | Stackoperation ein Fehler aufgetreten ist; die Prozedur erhaelt als     |
  | Parameter den Fehler vom Typ "StackResult" und den Namen der Prozedur,  |
  | in der der Fehler auftrat.                                              |
  | Nach Programmstart oder Aufruf von "UnAssignStackHandler" wird vom Modul|
  | kein Handler beim Auftritt eines Fehlers aktiviert.                     |
  |                                                                         |
  | Die automatische Fehlermeldung ist besonders in der Testphase zu emp-   |
  | fehlen, eine einfache Routine koennte z.B. so aussehen:                 |
  |                                                                         |
  | PROCEDURE Stackhandler( proc : ARRAY OF CHAR; fehler : StackResult );   |
  |   BEGIN                                                                 |
  |     WriteLn;                                                            |
  |     WriteString('Fehler bei Stackoperation - ');                        |
  |     WriteString('Prozedur '); WriteString(proc); Write(':');            |
  |     WriteLn;                                                            |
  |     CASE  fehler  OF                                                    |
  |      | stackOk   : WriteString('Alles ok');                             |
  |      | defErr    : WriteString('Der benutzte Stack ist undefiniert!');  |
  |      | sizeErr   :                                                      |
  |          WriteString('Das Datenelement hat einen anderen Speicher');    |
  |          WriteString('bedarf,'); WriteLn;                               |
  |          WriteString('als bei der Stackdefinition angegeben.');         |
  |      | noMem     : WriteString('Kein freier Speicher mehr.');           |
  |      | stackEmpty: WriteString('Der Stack ist leer.');                  |
  |      ELSE                                                               |
  |        WriteString('Totaler Zusammenbruch...');                         |
  |     END; (* CASE *)                                                     |
  |     WriteLn; WriteLn;                                                   |
  |   END  Stackhandler;                                                    |
   -------------------------------------------------------------------------*)


  PROCEDURE  LastStackResult ( ): StackResult;

 (*-------------------------------------------------------------------------
  | Liefert das Resultat der letzten Stackoperation, falls <done> nicht aus-|
  | reichen sollte oder fuer die Prozeduren "Length" und "IsEmpty", die     |
  | keinen Erfolgsparameter <done> haben.                                   |
  |                                                                         |
  | Moegliche Kombinationen sind:                                           |
  |  - stackOk    : Es ist kein Fehler aufgetreten. Moegliches Ergebnis     |
  |                 aller Prozeduren.                                       |
  |  - stackEmpty : Es wurde versucht, ein Element von einem leeren Stack   |
  |                 zu holen. Moegliches Ergebnis von "Pop", "TopOfStack"   |
  |                 und "Drop".                                             |
  |  - noMem      : der Speicher reicht nicht fuer die Ausfuehrung von      |
  |                 "Create" oder "Push".                                   |
  |  - sizeErr    : Es wurde versucht, ein Element auf dem Stack abzulegen  |
  |                 oder vom Stack zu holen, das eine andere Speicherplatz- |
  |                 groesse hat, als bei der Definition des Stacks angegeben|
  |                 wurde. Moegliches Ergebnis von "Pop","TopOfStack","Push"|
  |  - defErr     : Es wurde versucht, eine Stackoperation mit einer unde-  |
  |                 finierten Stackvariable auszufuehren. Moegliches Resul- |
  |                 tat aller Prozeduren ausser "Create".                   |
   -------------------------------------------------------------------------*)

(*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*)

  PROCEDURE  Create ((* EIN/ -- *)     groesse : CARDINAL;
                     (* EIN/ -- *)     blkElem : CARDINAL;
                     (* -- /AUS *) VAR stack   : Stack;
                     (* -- /AUS *) VAR done    : BOOLEAN  );

 (*-------------------------------------------------------------------------
  | Richtet einen <stack> und seine Verwaltung ein. <groesse> ist die       |
  | Groesse der Elemente, die auf dem Stack abgelegt werden sollen.         |
  | <blkElem> ist die Anzahl der Elemente, fuer die jeweils, wenn noetig,   |
  | ein neuer Speicherblock angefordert wird; ein grosser Wert fuer         |
  | <blkElem> fuert zu geringerem Verwaltungsaufwand, vergroessert aber den |
  | Anteil des Speichers, der die meiste Zeit nicht genutzt wird.           |
  | Die Prozedur muss vor allen anderen Stackoperationen ausgefuehrt werden;|
  | <stack> ist nur fuer Elemente der angegebenen Groesse zu benutzen.      |
  | <grosse> = 0, <blkElem> = 0 werden auf 1 korrigiert.                    |
  | <stack> ist immer mindestens einen Block gross.                         |
  |                                                                         |
  | Moegliche Fehler: noMem                                                 |
   -------------------------------------------------------------------------*)


  PROCEDURE  Delete ((* EIN/AUS *) VAR stack : Stack;
                     (* -- /AUS *) VAR done  : BOOLEAN );

 (*-------------------------------------------------------------------------
  | Gegenstueck zu "Create": <stack> wird aus der Verwaltung entfernt, und  |
  | der belegte Speicherplatz freigegeben.                                  |
  | <stack> hat nach Ausfuehrung den Wert NIL.                              |
  |                                                                         |
  | Moegliche Fehler: defErr                                                |
   -------------------------------------------------------------------------*)


  PROCEDURE  Clear ((* EIN/AUS *) VAR stack : Stack;
                    (* -- /AUS *) VAR done  : BOOLEAN );

 (*-------------------------------------------------------------------------
  | Entfernt saemtliche Elemente von <stack>, und gibt deren Speicherplatz  |
  | frei; <stack> selber bleibt erhalten.                                   |
  |                                                                         |
  | Moegliche Fehler: defErr                                                |
   -------------------------------------------------------------------------*)


  PROCEDURE  IsEmpty ((* EIN/ -- *) VAR stack : Stack ): BOOLEAN;

 (*-------------------------------------------------------------------------
  | Testet, ob <stack> leer ist.                                            |
  |                                                                         |
  | Moegliche Fehler: defErr                                                |
   -------------------------------------------------------------------------*)

  PROCEDURE  Length ((* EIN/ -- *) VAR stack : Stack ): CARDINAL;

 (*-------------------------------------------------------------------------
  | Liefert die Anzahl der Elemente von <stack>.                            |
  |                                                                         |
  | Moegliche Fehler: defErr                                                |
   -------------------------------------------------------------------------*)


  PROCEDURE  Push ((* EIN/ -- *)     wert  : ARRAY OF BYTE;
                   (* EIN/AUS *) VAR stack : Stack;
                   (* -- /AUS *) VAR done  : BOOLEAN       );

 (*-------------------------------------------------------------------------
  | Hiermit koennen Elemente auf dem Stack abgelegt werden. Der Datentyp,   |
  | fuer den der Stack genutzt werden kann, wird beim Aufruf von "Create"   |
  | festgelegt, d.h. alle weiteren Elemente, die auf den Stack 'gepushed'   |
  | werden, muessen auch von einem Typ sein, der den gleichen Speicherplatz |
  | belegt ( maschinenabhaengig ).                                          |
  |                                                                         |
  | Moegliche Fehler: defErr, sizeErr, noMem                                |
   -------------------------------------------------------------------------*)


  PROCEDURE  TopOfStack ((* EIN/ -- *) VAR stack : Stack;
                         (* -- /AUS *) VAR wert  : ARRAY OF BYTE;
                         (* -- /AUS *) VAR done  : BOOLEAN       );

 (*-------------------------------------------------------------------------
  | Liefert das oberste Element auf dem Stack; der Stack wird nicht veraen- |
  | dert. War der Stack leer, wird <wert> auf Null gesetzt.                 |
  |                                                                         |
  | Moegliche Fehler: defErr, sizeErr, stackEmpty                           |
   -------------------------------------------------------------------------*)


  PROCEDURE  Drop ((* EIN/AUS *) VAR stack : Stack;
                   (* -- /AUS *) VAR done  : BOOLEAN );

 (*-------------------------------------------------------------------------
  | Entfernt - ohne es zu liefern - das oberste Element von <stack>.        |
  |                                                                         |
  | Moegliche Fehler: defErr, stackEmpty                                    |
   -------------------------------------------------------------------------*)


  PROCEDURE  Pop ((* EIN/AUS *) VAR stack : Stack;
                  (* -- /AUS *) VAR wert  : ARRAY OF BYTE;
                  (* -- /AUS *) VAR done  : BOOLEAN       );

 (*-------------------------------------------------------------------------
  | Vereinigt "TopOfStack" und "Drop"                                       |
  |                                                                         |
  | Moegliche Fehler: defErr, sizeErr, stackEmpty                           |
   -------------------------------------------------------------------------*)

END  Stacks.
